Traditional linear hash tables optimize access time by evenly distributing records across the underlying table. In the process of entering records into the hash table, any logical ordering of the data is lost. While access time for a specific record given a specific key is fast, the ability to “walk” to adjacent logically ordered (not physically ordered in the hash table) is lost. Further, in the absence of a record existing in the hash table for a given key, due to the logical ordering of the data being lost on entry into the hash table, it is impossible to perform a time optimal “find nearest”, “find nearest preceding”, or “find nearest proceeding” type of query.
Referring now to FIG. 1, there is illustrated an example of the use of hashing to store and retrieve logically ordered data. In this example, employee records 1 include an employee name 2, and a social security number 3 used as key k for a hash function F(k) used to map employee records 1 to a hash table 4 with an Index 5 space of 2000 (0-1999). Records 1 are logically ordered according to social security number. As illustrated in FIG. 1, records 1 are mapped, in this example, with hash function F(k) (which may be any arbitrary function), as follows:
TABLE 1Social SecurityHash TableNext RecordPrevious RecordNumberIndexPointerPointer310-54-098610021998N/A356-48-1123199811002470-70-0258119961998480-82-5614199610001492-57-13491000N/A1996As further illustrated in FIG. 1 and Table 1 above, each record in the hash table is threaded by the inclusion of pointers 6 to the next succeeding and next preceding logically ordered record. In FIGS. 1 and 3, pointers with arrows on both ends represent both the “next” and “previous” record pointers between records. With this threading, it is possible to “walk” to adjacent logically ordered records by following pointers 6.
While the threaded linear hashing table example described above provides for optimized access time by allowing records to be located with a single hashing operation, and also provides the ability to walk the records in the table in logical order using pointers, a problem still remains in locating a record logically nearest a particular key where there is no record in the hash table corresponding to the key. For example, if one were to attempt to locate the nearest preceding logical record with the key 474-56-0789, the hashing function may point to a record in the hash table with the Index 1854. In the example of FIG. 1, no record exists at this Index, and thus it is not possible to enter the hash table at the index and walk to the nearest preceding record. Thus, this record may only be found by walking through the entire table, beginning with the first record (which, assuming that the table contains thousands or hundreds of thousands of records is likely very inefficient), or hashing each of the possible keys on the preceding record side of the key 474-56-0789, until a hashing operation locates a record. In this example, such a search would require hashing all of the keys in the range between 474-56-0789 and 470-70-0258. Again, this is an inefficient manner in which to locate the nearest logical record. Accordingly, there is a need for a more efficient system for locating a nearest logical record in a hash table where no record exists for the designated key.